package com.gitee.feizns.explore.data_structure.array.easy;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * 532. 数组中的K-diff数对
 * @author feizns
 * @since 2020/1/10
 */
public class FindPairs {

    public static void main(String[] args) {
        System.out.println(findPairs3(new int[]{1,3,1,5,4}, 0));
    }

    public static int findPairs(int[] num, int k) {
        Set<String> pairs = new HashSet<>();
        Arrays.sort(num);
        int ret = 0;
        for (int j = 1, p = 0; j < num.length; j++) {
            if ( num[j] - num[p] == k ) {
                if ( !pairs.contains(num[j] + "-" + num[p]) ) {
                    pairs.add(num[j] + "-" + num[p]);
                    ret++;
                }
            } else if ( num[j] - num[p] < k )
                continue;
            p++;
            if ( p < j )
                j--;
        }
        return ret;
    }

    public static int findPairs2(int[] num, int k) {
        Arrays.sort(num);
        int r = 0;
        int l = 0;
        Integer p = null;
        for (int i = 1; i < num.length; i++) {
            if ( num[i] - num[l] == k ) {
                p = num[l++];
                r++;
            } else if ( num[i] - num[l] > k || p == num[l] ) {
                if ( ++l != i ) i--;
            }
        }
        return r;
    }

    public static int findPairs3(int[] num, int k) {
        Set<Integer> saw = new HashSet<>();
        Set<Integer> diff = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            if ( saw.contains(num[i] - k) )
                diff.add(num[i] - k);
            if ( saw.contains(num[i] + k) )
                diff.add(num[i]);
            saw.add(num[i]);
        }
        return diff.size();
    }

}
